package alo.p6.work;

import org.junit.Test;
import alo.p6.BinaryTreeNode;

import java.util.Stack;

/**
 * @ClassName Zigzag
 * @Description Zigzag树的遍历
 * @Author Fanxc
 * @DATE 2021/1/31 13:49
 * @Version 1.0
 */
public class Zigzag {
    void zigzag(BinaryTreeNode root){
        BinaryTreeNode temp;
        //使用两个栈来代表奇偶层，分布采用不同的顺序输出
        Stack<BinaryTreeNode> stack1=new Stack<>();
        Stack<BinaryTreeNode> stack2=new Stack<>();
        stack1.push(root);
        int curLevel=1;
        while (!stack1.isEmpty()||!stack2.isEmpty()){
            if (curLevel%2==1) {
                while (!stack1.isEmpty()) {
                    temp = stack1.pop();
                    System.out.print(temp.getData()+" ");
                    //奇数level，先左后右
                    if (temp.getLeft()!=null) {
                        stack2.push(temp.getLeft());
                    }
                    if (temp.getRight()!=null) {
                        stack2.push(temp.getRight());
                    }

                }
            }else {
                while (!stack2.isEmpty()){
                    temp=stack2.pop();
                    System.out.print(temp.getData()+" ");
                    //偶数level，先右后左
                    if (temp.getRight() != null) {
                        stack1.push(temp.getRight());
                    }
                    if (temp.getLeft() != null) {
                        stack1.push(temp.getLeft());
                    }
                }
            }
            curLevel++;
        }
    }
    @Test
    public void test() {
        int[] A = {1, 2, 4, 5, 3, 6, 7};
        int[] B = {4, 2, 5, 1, 6, 3, 7};
        BuildBinaryTree buildBinaryTree = new BuildBinaryTree();
        BinaryTreeNode root = buildBinaryTree.buildBinaryTree(B, A, 0, 6);
        zigzag(root);//1 3 2 4 5 6 7
    }
}
